package guide;

import org.junit.Test;

/**
 * @author fance
 * @date 18-4-13 上午10:40
 */
public class DP {
    // 台阶 n-1 n-2  生牛 n-1 n-3  关键分析最优子结构,是否存在重叠子问题. 写出状态转移方程


    public long fibI(int n) {
        if (n < 1) {
            return  0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return fibI(n - 1) + fibI(n - 2);
    }
    public long fibII(int n) {
        if (n < 1) {
            return  0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        long first = 2;
        long second = 1;
        long res = 0;
        for (int i = 3; i <= n; i++) {
            res = first + second;
            second = first;
            first = res;
        }
        return res;
    }

    public long getCowI(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }

        return getCowI(n - 1) + getCowI(n - 3);
    }
    public long getCowII(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        long res = 3;
        long pre = 2;
        long prepre = 1;
        long tmp1 = 0;
        long tmp2 = 0;
        for (int i = 4; i <= n; i++) {
            tmp1 = res;
            tmp2 = pre;
            res = res + prepre;
            pre = tmp1;
            prepre = tmp2;
        }
        return res;
    }

    public int minPathSumI(int [][] m) {
        if (m == null || m.length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + m[0][i];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }

    // 换钱最少张数可用任意张
    public int minCoinsI(int[] a, int aim) {
        if (a == null || a.length == 0 || aim < 0) {
            return -1;
        }
        int n = a.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][aim + 1];
        for (int i = 1; i <= aim; i++) {
            dp[0][i] = max;
            if (i - a[0] >= 0 && dp[0][i - a[0]] != max) {
                dp[0][i] = dp[0][i - a[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                left = max;
                if (j - a[i] >= 0 && dp[i][j - a[i]] != max) {
                    left = dp[i][j - a[i]] + 1;
                }

                dp[i][j] = Math.min(left, dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
    }
    // 可用一张
    public int minCoinsIII(int[] a, int aim) {
        if (a == null || a.length == 0 || aim < 0) {
            return -1;
        }
        int n = a.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][aim + 1];
        for (int i = 1; i <= aim; i++) {
            dp[0][i] = max;
        }
        if (a[0] <= aim) {
            dp[0][a[0]] = 1;
        }

        int leftup = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                leftup = max;
                if (j - a[i] >= 0 && dp[i][j - a[i]] != max) {
                    leftup = dp[i][j - a[i]] + 1;
                }

                dp[i][j] = Math.min(leftup, dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
    }

    // 换钱方法数暴力递归
    public int coinsI(int[] a, int aim) {
        if (a == null || a.length == 0 || aim < 0) {
            return 0;
        }
        return processI(a, 0, aim);
    }
    private int processI(int [] a, int index, int aim) {
        int res = 0;
        if (index == a.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            for (int i = 0; i * a[index] <= aim; i++) {
                res += processI(a, index + 1, aim - a[index] * i);
            }
        }
        return res;
    }
    // 记忆化搜索
    public int coinsII(int[] a, int aim) {
        if (a == null || a.length == 0 || aim < 0) {
            return 0;
        }
        int[][] map = new int[a.length + 1][aim + 1];
        return processII(a, 0, aim, map);
    }
    private int processII(int [] a, int index, int aim, int[][] map) {
        int res = 0;
        if (index == a.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            int mapVal = 0;
            for (int i = 0; i * a[index] <= aim; i++) {
                mapVal = map[index + 1][aim - a[index] * i];
                if (mapVal != 0) {
                    res += mapVal == -1 ? 0 : mapVal;
                } else {
                    res += processII(a, index + 1, aim - a[index] * i, map);
                }
            }
        }
        map[index][aim] = res == 0 ? -1 : res;
        return res;
    }
    // dp
    public int coinsIII(int[] a, int aim) {
        if (a == null || a.length == 0 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[a.length][aim + 1];
        for (int i = 0; i < a.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; a[0] * i <= aim; i++) {
            dp[0][a[0] * i] = 1;
        }
        int num = 0;
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j <= aim; j++) {
                num = 0;
                for (int k = 0; j - a[i] * k >= 0; k++) {
                    num += dp[i - 1][j - a[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[a.length - 1][aim];
    }

    // LIS 最长递增子序列
    private int[] getDpForLIS(int[] a) {
        int[] dp = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }
    public int[] LIS(int[] a, int[] dp) {
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }

        int[] lis = new int[len];
        lis[--len] = a[index];
        for (int i = index; i >= 0; i--) {
            if (a[i] < a[index] && dp[i] == dp[index] - 1) {
                lis[--len] = a[i];
                index = i;
            }
        }
        return lis;
    }

    // LCSE 最长公共子序列
    private int[][] getDpForLcse(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
        }
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], str1[0] == str2[i] ? 1 : 0);
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp;
    }
    public String lcse(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return "";
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int[][] dp = getDpForLcse(chars1, chars2);
        int m = chars1.length - 1;
        int n = chars2.length - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;
        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                m--;
            } else {
                res[index--] = chars1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);
    }

    // 最长公共子串
    private int[][] getDpForLcst(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < str2.length; i++) {
            if (str1[0] == str2[i]) {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp;
    }
    public String lcst(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return "";
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int[][] dp = getDpForLcst(chars1, chars2);
        int end = 0;
        int max = 0;
        for (int i = 0; i < chars1.length; i++) {
            for (int j = 0; j < chars2.length; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    end = i;
                }
            }
        }
        return s1.substring(end - max + 1, end + 1);
    }

    // 最小编辑距离
    public int minCost(String s1, String s2, int ic, int dc, int rc) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int rows = chars1.length + 1;
        int cols = chars2.length + 1;
        int[][] dp = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            dp[i][0] = dc * i;
        }
        for (int i = 0; i < cols; i++) {
            dp[0][i] = ic * i;
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }

                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
        return dp[rows - 1][cols - 1];
    }


    // N皇后问题
    public int NQueue(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process(0, record, n);
    }
    private int process(int i, int[] record, int n) {
        if (i == n) {
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process(i + 1, record, n);
            }
        }
        return res;
    }
    private boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }


    // 数字字符串转化为字母组合的种类 1.递归 2.dp
    public int num1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        return num1Process(chars, 0);
    }
    private int num1Process(char[] chars, int i) {
        if (i == chars.length) {
            return 1;
        }
        if (chars[i] == '0') {
            return 0;
        }
        int res = num1Process(chars, i + 1);
        if (i + 1 < chars.length && (chars[i] - '0') * 10 + chars[i + 1] - '0' < 27) {
            res += num1Process(chars, i + 2);
        }
        return res;
    }
    // dp  并不理解
    public int num2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int cur = chars[chars.length - 1] == '0' ? 0 : 1;
        int next = 1;
        int tmp = 0;
        for (int i = chars.length - 2; i >= 0; i--) {
            if (chars[i] == '0') {
                next = cur;
                cur = 0;
            } else {
                tmp = cur;
                if ((chars[i] - '0') * 10 + chars[i + 1] - '0' < 27) {
                    cur += next;
                }
                next = tmp;
            }
        }
        return cur;
    }
    @Test
    public void test() {
        System.out.println(getCowI(10));
        System.out.println(getCowII(10));
        /*int[] a = {5,10,25,1, 2};
        int[] res = LIS(a, (a));
        for (int n: res
             ) {
            System.out.print(n + " ");
        }
        System.out.println();
        long st = System.currentTimeMillis();
        System.out.println();
        System.out.println(System.currentTimeMillis() - st);
        System.out.println(lcse("abc", "asdfc"));*/
        /*System.out.println(minCost("abc", "adc", 5, 3, 2));
        System.out.println(NQueue(8));*/
    }
}
